package com.haidechizi.sort;

import java.util.Arrays;

/**
 * @author: wangdejun
 * @create: 2020-01-10 15:20
 * <p>
 * 基数排序
 **/
public class RadixSort {

    public static void main(String[] args) {
        int[] arr = new int[]{37, 7, 345, 87, 6, 62, 71, 792, 9, 99999};
        System.out.println(Arrays.toString(arr));
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 基数排序
     * 1.先按照各位数进行排序
     * 2.按照十位数进行排序
     * 3.按照百位数进行排序
     * ...
     *
     * @param arr
     */
    public static void radixSort(int[] arr) {
        // 获取最大的值
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }

        // 获取最大数是几位数
        //int[][] radixArr = new int[10][arr.length];
        int maxLength = (max + "").length();
        for (int i = 0, n = 1; i < maxLength; i++, n = n * 10) {
            // 定义二维数组,防止数据
            int[][] radixArr = new int[10][arr.length];
            // 没录每个二维数组中放置的数据
            int[] count = new int[10];
            // 循环每个数据，将每个数据，根据位数，将数据放入二维数组中
            for (int j = 0; j < arr.length; j++) {
                int yushu = arr[j] / n % 10;
                radixArr[yushu][count[yushu]] = arr[j];
                count[yushu]++;
            }
            // 将二维数组中的数据放入到原数组中
            int index = 0;
            for (int k = 0; k < count.length; k++) {
                if (count[k] > 0) {
                    for (int m = 0; m < count[k]; m++) {
                        arr[index] = radixArr[k][m];
                        index++;
                    }
                }
            }
        }
    }
}
